//
//  Problem541.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 541. 反转字符串 II 【字符位置替换】
 给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

 如果剩余字符少于 k 个，则将剩余字符全部反转。
 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
  
 示例:
    输入: s = "abcdefg", k = 2
    输出: "bacdfeg"
 提示：
     该字符串只包含小写英文字母。
     给定字符串的长度和 k 在 [1, 10000] 范围内。

 */
@objcMembers class Problem541: NSObject {
    func solution() {
        print(reverseStr("abcdefg", 2))
    }
    
    /*
     遍历字符串
     1: 创建一个指针i、一个插入位置j、一个Bool isZheng
     2: 当i>k时，该字符在j处插入（前k反转） i+=1
     3: 当i=k时，在结尾处插入（后k不变）i-=1， j = i
     4: 当i=0时，重复2，
     */
    func reverseStr(_ s: String, _ k: Int) -> String {
        var I = 0   // 遍历指针
        var J = 0
        var isZheng = false
        var str = ""
        for (i, c) in s.enumerated() {
            if I == 0 {
                J = i
                str.insert(c, at: str.index(str.startIndex, offsetBy: J))
                I += 1
                isZheng = false
                
            } else if I == k {
                str.append(c)
                I -= 1
                isZheng = true
            } else if isZheng == false {
                str.insert(c, at: str.index(str.startIndex, offsetBy: J))
                I += 1
            } else if isZheng == true {
                str.append(c)
                I -= 1
            }
        }
        
        return str
    }
    
    /*
     1:转换成字符数组charts
     2:前k个反转，然后跳过k个
     */
    func reverseStrOther(_ s: String, _ k: Int) -> String {
        var a:Array<Character> = Array(s)
        var i = 0
        while i < a.count{
            let r = i + k - 1       // 计算前k的结束位置 r
            if (r < a.count){
                reverseArray(array:&a,l:i,r:r)
            }else{
                reverseArray(array:&a,l:i,r:a.count-1)
            }
            i = i + 2 * k       // 每次跨2k个
        }
        return String(a)
    }
    
    // 这里使用了 双指针，加快速度
    func reverseArray(array: inout Array<Character>, l: Int, r: Int){
        var left = l
        var right = r
        while left < right {
            let temp = array[left]
            array[left] = array[right]
            array[right] = temp
            left += 1
            right -= 1
        }
    }
}
